//输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 
//
// 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 
//
// 
//
// 示例 1： 
//
// 输入：target = 9
//输出：[[2,3,4],[4,5]]
// 
//
// 示例 2： 
//
// 输入：target = 15
//输出：[[1,2,3,4,5],[4,5,6],[7,8]]
// 
//
// 
//
// 限制： 
//
// 
// 1 <= target <= 10^5 
// 
//
// 
// Related Topics 数学 双指针 枚举 👍 368 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class HeWeiSdeLianXuZhengShuXuLieLcof {
    public static void main(String[] args) {
        Solution solution = new HeWeiSdeLianXuZhengShuXuLieLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         *输出所有和为target的连续子序列
         *  输入：target = 15
         *  输出：[[1,2,3,4,5],[4,5,6],[7,8]]
         * 最直观的方法：直接遍历所有可能的情况，但是时间复杂度不是很理想
         */
        public int[][] findContinuousSequence1(int target) {
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 1; i <= target / 2; i++) {
                List<Integer> temp = new ArrayList<>();
                int sum = 0;
                for (int j = i; j < target; j++) {
                    temp.add(j);
                    sum += j;
                    if (sum == target) {
                        list.add(temp);
                        break;
                    }
                    else if (sum > target) break;
                }
            }
            int[][] res = new int[list.size()][];
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i).stream().mapToInt(Integer::intValue).toArray();
            }
            return res;
        }
        /**
         * 知识迁移：使用两个值保存连续数组的两个边界值（双指针滑动窗口）
         * 使用左右指针表示窗口边界
         * 根据当前窗口和s和target进行对比
         * 如果sum>target left++以缩小窗口值
         * 如果sum<target right++以扩大窗口值
         * 如果sum==target的时候就进行添加，且左边界右移
         */
        public int[][] findContinuousSequence(int target) {
            List<int[]> res = new ArrayList<>();
            int left = 1, right = 2, sum = 3;
            while (left < right){
                if (sum == target){
                    int[] ans = new int[right - left + 1];
                    for (int i = left; i <= right; i++) ans[i - left] = i;
                    res.add(ans);
                }
                if (sum >= target){
                    sum -= left;
                    left++;
                }else {
                    right++;
                    sum += right;
                }
            }
            return res.toArray(new int[0][]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}